#include<iostream>
#include<vector>
#include<string>
using namespace std;

//509.斐波那契数列
//方法一：记忆化搜索方式
vector<int> memory;
int dfs(int n){
    //如果当前值已存在备忘录中，直接返回
    if(memory[n]!=-1){
        return memory[n];
    }

    //递归出口
    if(n==1||n==0){
        memory[n] = n;
        return memory[n];
    }

    //先存放到备忘录中再返回
    memory[n] = dfs(n - 1) + dfs(n - 2);
    return memory[n];
}
int fib(int n){
    //先将备忘录中的值全部初始化为-1
    memory.resize(31, -1);
    //记忆化搜索
    return dfs(n);
}
//方法二：动态规划
int dp[31];
int fib(int n){
    //先初始化状态转移方程
    dp[0] = 0;
    dp[1] = 1;

    //填表
    for (int i = 2; i < 31;i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

//62.不同路径
//方式一：记忆化搜索
//创建一个备忘录
vector<vector<int>> memory;
int dfs(int i,int j){
    //如果备忘录中存在直接返回
    if(memory[i][j]!=0){
        return memory[i][j];
    }

    //处理越界情况
    if(i==0||j==0){
        return memory[i][j];
    }
    //处理递归出口，也就是起点位置
    if(i==1&&j==1){
        memory[i][j]=1;
        return memory[i][j];
    }

    //记忆化搜索，找上和左两个方向的位置,先存放到备忘录中再返回
    memory[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
    return memory[i][j];
}
int uniquePaths(int m, int n){
    //先初始化备忘录
    memory.resize(m + 1, vector<int>(n + 1));

    //dfs函数表示从起点到该点共有多少种路线
    return dfs(m, n);
}


//300.最长递增子序列
//方式一：记忆化搜索
vector<int> memory;
int dfs(vector<int>& nums,int pos){
    //如果当前位置的增长递增子序列个数已经存在备忘录中，直接返回
    if(memory[pos]!=0){
        return memory[pos];
    }
    int ret = 1;
    for (int i = pos + 1; i < nums.size(); i++){
        if(nums[i]>nums[pos]){
            ret = max(ret, dfs(nums, i) + 1);
        }
    }

    //先将当前位置的个数存放到备忘录中再返回
    memory[pos] = ret;
    return ret;
}
int lengthOfLIS(vector<int>& nums){
    //初始化备忘录
    memory.resize(nums.size());

    //枚举所有起点位置的递增子序列的个数，找到最大的
    int ret = 0;
    for (int i = 0; i < nums.size(); i++){
        ret = max(ret, dfs(nums, i));
    }

    return ret;
}

//375.猜数字大小2
//创建一个备忘录，因为存在区间相同，所以以二维数组的形式表示
vector<vector<int>> memory;
int dfs(int left,int right){
    //处理递归出口
    if(left>=right){
        return 0;
    }
    //如果当前区间的结果存在备忘录中，直接返回
    if(memory[left][right]!=-1){
        return memory[left][right];
    }

    //枚举区间[left,right]所有的中间节点
    int ret = 0;
    for (int i = left; i <= right; i++){
        int leftret = dfs(left, i - 1);
        int rightret = dfs(i + 1, right);
        //先取当前i中的左右两个区间的最大值+i
        //再取所有i情况中的最小值
        ret =min(ret, max(leftret, rightret)+1);
    }

    memory[left][right]=ret;
    return ret;
}
int getMoneyAmount(int n){
    if(n==1){
        return 0;
    }
    //先初始化备忘录，全部设置为-1
    memory.resize(n + 1);
    for (int i = 0; i < n + 1; i++){
        memory[i].resize(n + 1, -1);
    }

    return dfs(1,n);
}

//329.矩阵中的最长递增路径
int memory[201][201];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n = 0, m = 0;
int dfs(vector<vector<int>>& matrix,int i,int j){
    if(memory[i][j]!=0){
        return memory[i][j];
    }

    //初始值设置为1，一定存在最后一个数四个相邻位置都没有比它小的
    int ret = 1;
    for (int k = 0; k < 4; k++){
        int x = i + dx[k], y = j + dy[k];
        if(x>=0&&x<n&&y>=0&&y<m&&matrix[x][y]>matrix[i][j]){
            ret = max(ret, dfs(matrix, x, y) + 1);
        }
    }
    
    memory[i][j]=ret;
    return ret;
}
int longestIncreasingPath(vector<vector<int>>& matrix){
    n = matrix.size(), m = matrix[0].size();

    int ret = 0;
    //枚举所有位置的路径，找出最长的
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            ret = max(ret, dfs(matrix,i, j));
        }
    }
    return ret;
}

int main(){

    return 0;
}